import bean.ListNode;

public class LeetCode328 {
    public static void main(String[] args) {
        LeetCode328 leetCode328 = new LeetCode328();
        ListNode head =  leetCode328.oddEvenList(ListNode.createListNodes(new int[]{1}));
        ListNode.printNodeList(head);
    }

    /**
     * 思路：
     * 1.步进法
     * 2.定义index1指向奇数尾部索引，定义index2指向偶数尾部索引，step指向下一次处理奇数和偶数开始位置
     * 3.从step开始，取step和step.next分别放到index1（此时index1的next应保存到一个临时变量temp中）和index2的next变量中，
     *  然后将index1 = index1.next,index2 = index2.next, index1.next = temp
     *
     *
     * @param head
     * @return
     */
    public ListNode oddEvenList(ListNode head) {
        if (head == null){
            return head;
        }

        ListNode index1 = head;
        if(head.next == null){
            return head;
        }

        ListNode index2 = head.next;
        if(index2.next == null){
            return head;
        }

        ListNode step = index2.next;

        while (step != null){
            ListNode temp = index1.next;
            ListNode tempStep2 = step.next;
            index1.next = step;
            index1 = index1.next;
            index1.next = temp;

            if(tempStep2 != null){
                index2.next = tempStep2;
                index2 = index2.next;

                step = index2.next;

            }else {
                index2.next = null;
                return head;
            }

        }

        return head;
    }
}
